package com.lagou.algorithmus;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 双指针
 */
public class AlgorithmusTwoIndex {
    public static void main(String[] args) {
        int[] arr = {-1,0,1,2,-1,-4};
        threeSum(arr);

    }

    /**
     * 三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组
     * [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * 你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 排序数组
        Arrays.sort(nums);
        // 三元值的和转换为二元值的思维
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -nums[i];
            // 右指针
            int right = nums.length - 1;
            // 中间指针即局部左指针
            int left = i + 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    List<Integer> answer = new ArrayList<>();
                    answer.add(nums[i]);
                    answer.add(nums[left]);
                    answer.add(nums[right]);
                    result.add(answer);
                    right--;
                } else if (nums[left] + nums[right] > target) {
                    // 右指针移动
                    right--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }

    /**
     * 盛水最多的容器
     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     * 最大水容量即是求 最大面积 = 长（index） * 宽(num[index]) 两个指针指向的数字中较小值∗指针之间的距离
     */
    public static int maxArea(int[] height) {
        // 利用双指针 左右指针的差值  优先移动两指针中值小的那一个
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        while (left < right) {
            int width = Math.min(height[left], height[right]);
            int area = (right - left) * width;
            result = Math.max(area, result);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }

    /**
     * 给定一个数组 height，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * height = [1,2,3,4,0,1,2,2,3,0,3,12]
     */
    public static void moveZeroes(int[] height) {
        for (int i = 0; i < height.length; i++) {
            if (height[i] == 0) {
                for (int j = i + 1; j < height.length; j++) {
                    if (height[j] != 0) {
                        height[i] = height[j];
                        height[j] = 0;
                        break;
                    }
                }
            }
        }
    }
}
